package listbyorder.access001_100.test79;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/4 10:54
 */
public class Solution1 {

    // 方法一：暴力递归
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) return false;
        int m = board.length;
        int n = board[0].length;
        boolean[][] flag = new boolean[m][n];
        char c = word.charAt(0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == c && getAns(board, i, j, m, n, flag, word, 0, word.length())) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean getAns(char[][] board, int r, int c, int m, int n, boolean[][] flag, String word, int s, int e) {
        if (s == e) return true;
        if (r == m || c == n || r < 0 || c < 0) return false;
        if (flag[r][c]) return false;
        if (board[r][c] == word.charAt(s)) {
            flag[r][c] = true;
            if (getAns(board, r + 1, c, m, n, flag, word, s + 1, e)
                    || getAns(board, r, c + 1, m, n, flag, word, s + 1, e)
                    || getAns(board, r - 1, c, m, n, flag, word, s + 1, e)
                    || getAns(board, r, c - 1, m, n, flag, word, s + 1, e)) {
                return true;
            }
            flag[r][c] = false;
        }
        return false;
    }

}
